/* zpipe.c: example of proper use of zlib's inflate() and deflate()
 Not copyrighted -- provided to the public domain
 Version 1.4  11 December 2005  Mark Adler */

/* Version history:
 1.0  30 Oct 2004  First version
 1.1   8 Nov 2004  Add void casting for unused return values
 Use switch statement for inflate() return values
 1.2   9 Nov 2004  Add assertions to document zlib guarantees
 1.3   6 Apr 2005  Remove incorrect assertion in inf()
 1.4  11 Dec 2005  Add hack to avoid MSDOS end-of-line conversions
 Avoid some compiler warnings for input and output buffers
 */
extern "C"{
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <zlib.h>



#if defined(MSDOS) || defined(OS2) || defined(WIN32) || defined(__CYGWIN__)
#  include <fcntl.h>
#  include <io.h>
#  define SET_BINARY_MODE(file) setmode(fileno(file), O_BINARY)
#else
#  define SET_BINARY_MODE(file)
#endif

#define CHUNK 16384
}

#include <iostream>
#include <fstream>
#include <sstream>
#include <deque>
using namespace std;
/* Compress from file source to file dest until EOF on source.
 def() returns Z_OK on success, Z_MEM_ERROR if memory could not be
 allocated for processing, Z_STREAM_ERROR if an invalid compression
 level is supplied, Z_VERSION_ERROR if the version of zlib.h and the
 version of the library linked do not match, or Z_ERRNO if there is
 an error reading or writing the files. */
int def(FILE *source, FILE *dest, int level)
{

    int ret, flush;
    unsigned have;
    z_stream strm;
    unsigned char in[CHUNK];
    unsigned char out[CHUNK];
    
    /* allocate deflate state */
    strm.zalloc = Z_NULL;
    strm.zfree = Z_NULL;
    strm.opaque = Z_NULL;
    ret = deflateInit(&strm, level);
    if (ret != Z_OK)
        return ret;
    
    /* compress until end of file */
    do {
        strm.avail_in = fread(in, 1, CHUNK, source);
        if (ferror(source)) {
            (void)deflateEnd(&strm);
            return Z_ERRNO;
        }
        flush = feof(source) ? Z_FINISH : Z_NO_FLUSH;
        strm.next_in = in;
        
        // BENSON: Where I start making the changes to translate the x's.

        
        ofstream myfile;
        myfile.open ("example.txt"); // BENSON: Text file contains all iterations of the translations of the most recent chunk.
                                     // BENSON: A chunk is defined on line 30 as either 16kb or 32kb.
                                     // BENSON: So this file will contain the most recent chunk of 
                                     // BENSON: the test data with the converted x's to either 1s or 0s.
                                     // BENSON: e.g. If the there are 40kb worth of characters. It will show the step-by-step
                                     // BENSON: translations of the last 8kb of charactrers.
                                     // BENSON: For instance, the first paragraph of characters will be the original data.
                                     // BENSON: The 2nd paragraph of characters will show the converted terms with respect
                                     // BENSON: to the moving window. Thus the last paragraph will contain the translated 
                                     // BENSON: test data that is sent to the LZ77 compression.

        deque <char> window;         // BENSON: Establish sliding window. The size of the window dynamically increases 
                                     // BENSON: size in the for loop starting in line 113.
        
        if(strm.next_in[0] == 'x'){  // BENSON: strm.next_in is the pointer to the array of characters being read in.
            strm.next_in[0] = '1';   // BENSON: strm.next_in is defined in line 69.
                                     // BENSON: If the first character of the array is an "x", set it to 1.
                                     // BENSON: I do this because there are no characters in the sliding window.
        }
        
        for(int i = 0; i < strm.avail_in;){ // BENSON: strm.avail_in is the number of characters that are going to compressed.
                                            // BENSON: That max size of strm.avail_in is CHUNK. 
                                            // BENSON: strm.avail_in is defined in line 63.
                                            // BENSON: This is the outermost for-loop.

            int high = 1;                   // BENSON: Resets "high" variable. Used as a placeholder for the longest matched string.
                                            // BENSON: 1 serves as a temporary value

            int placement = -1;             // BENSON: Resets "placement" variable. I chose a number less than 0.
       


            for(int j = (window.size()-1); j >= 0; j--){ // BENSON: Start at the end of the sliding window array
                                                         // BENSON: Iterate from the end to the front.
                                                         // BENSON: Originally 0 (I think).

                int keep = 0;                            // BENSON: Sets "keep" variable.
                                                         // BENSON: Used as a counter for the length of the matched string

                if(window[j] == strm.next_in[i] || (strm.next_in[i] == 'x')){ // BENSON: If match or 'x' found.

                    int I = i;    // BENSON:  Declare's "I"; used as index of the match in the "look-ahead buffer".                                                                   
                    keep ++;      // BENSON:  Add 1 because length of matched string is 1.
                    int plus = 1; // BENSON:  Sets "plus" variable


                    while(((strm.next_in[I+1] == window[j + plus]) && ((j + plus) < window.size())) || ((strm.next_in[I + 1] == 'x') && ((j + plus) < window.size()))){
                        // BENSON: Continue to find the longest match if match found.
                        // BENSON: Considers sliding window.size, but needs to be limited by "search buffer" size.
                        // BENSON: sliding window is the same as "search buffer"

                        // BENSON: IMPT NOTE: NEED TO FIND SEARCH BUFFER MAX SIZE.

                        keep ++; // BENSON: Equals length of matched string.

                        I++;     // BENSON: Increase to the next index of longest matched string.
                                 // BENSON: "I" needs to be limited by "look-ahead buffer" size.
                                 // BENSON: IMPT NOTE: NEED TO FIND LOOK-AHEAD BUFFER MAX SIZE.

                        plus++;  // BENSON: "j+plus" represents the index of the character proceeding the index of the original matched
                                 // BENSON: character. 
                                 // BENSON: IMPT NOTE: "j+plus" needs to be smaller than "search buffer" size (line 123).



                    }
                }
                if(keep >= high){ // BENSON: Keeps matched string w/longest length starting at character: "strm.next_in[i]".

                    high = keep;  // BENSON: high = string length. relevant for the next nexted for loop.

                    placement = j; // BENSON: placement = index in sliding window. Used to hold the value
                                   // BENSON: "Placement" is relevant in the next for loop.
                }
            }
            

            for(int j = (window.size()-1); j >= 0; j--){
                if(j == placement){
                    for(int k = 0; k < high; k++){
                        strm.next_in[k+i] = window[j+k]; 

                        // BENSON: By iterating through the sliding window in line 152, we can locate the index (placement)
                        // BENSON: in the sliding window that provides the longest matching string. (line 153)
                        // BENSON: The matching string is then set equal to the string found in the sliding window (line 154).
                        // BENSON: This is the forloop where the actually "x" translations occur.
                    }
                }
            }
            
                    
            for(int l = 0; l  < high; l++){ // BENSON: Move matched/translated strings into sliding window
                window.push_back(strm.next_in[l+i]);
                
            }
            
            
            i = i + high; // BENSON: "i" increases by string length so that the outermost for loop (line 95) starts 
                          // BENSON: further along in the strm.next_in.
            
            for(int i = 0; i < strm.avail_in; i++){
                myfile << strm.next_in[i]; //BENSON: Outputs currently translated string chunk.
            }
            myfile << "\n";
            

        }
        
        // BENSON: Displays completed translation of final chunk in text file.
        myfile << "strm.avail_in: " << strm.avail_in << "\n";
        myfile << "CHUNK: " << CHUNK << "\n";
        for(int i = 0; i < strm.avail_in; i++){
            myfile << strm.next_in[i];
        }

            // BENSON: Used for comparing compressions withs x's as 1s and x's as 0s.
//         for(int i = 0; i < strm.avail_in; i++){
//             if(strm.next_in[i] == 'x'){
//                 strm.next_in[i] = '1';
//             }
//         }

        myfile.close();
        //BENSON: Where I stop making changes.
        
        
        /* run deflate() on input until output buffer not full, finish
         compression if all of source has been read in */
        do {

            strm.avail_out = CHUNK;
            strm.next_out = out;
            ret = deflate(&strm, flush);    /* no bad return value */
            assert(ret != Z_STREAM_ERROR);  /* state not clobbered */
            have = CHUNK - strm.avail_out;
            if (fwrite(out, 1, have, dest) != have || ferror(dest)) {
                (void)deflateEnd(&strm);
                return Z_ERRNO;
            }
        } while (strm.avail_out == 0);
        assert(strm.avail_in == 0);     /* all input will be used */
        
        /* done when last data in file processed */
    } while (flush != Z_FINISH);
    assert(ret == Z_STREAM_END);        /* stream will be complete */
    
    /* clean up and return */
    (void)deflateEnd(&strm);
    return Z_OK;
}

/* Decompress from file source to file dest until stream ends or EOF.
 inf() returns Z_OK on success, Z_MEM_ERROR if memory could not be
 allocated for processing, Z_DATA_ERROR if the deflate data is
 invalid or incomplete, Z_VERSION_ERROR if the version of zlib.h and
 the version of the library linked do not match, or Z_ERRNO if there
 is an error reading or writing the files. */
int inf(FILE *source, FILE *dest)
{
    int ret;
    unsigned have;
    z_stream strm;
    unsigned char in[CHUNK];
    unsigned char out[CHUNK];
    
    /* allocate inflate state */
    strm.zalloc = Z_NULL;
    strm.zfree = Z_NULL;
    strm.opaque = Z_NULL;
    strm.avail_in = 0;
    strm.next_in = Z_NULL;
    ret = inflateInit(&strm);
    if (ret != Z_OK)
        return ret;
    
    /* decompress until deflate stream ends or end of file */
    do {
        strm.avail_in = fread(in, 1, CHUNK, source);
        if (ferror(source)) {
            (void)inflateEnd(&strm);
            return Z_ERRNO;
        }
        if (strm.avail_in == 0)
            break;
        strm.next_in = in;
        
        /* run inflate() on input until output buffer not full */
        do {
            strm.avail_out = CHUNK;
            strm.next_out = out;
            ret = inflate(&strm, Z_NO_FLUSH);
            assert(ret != Z_STREAM_ERROR);  /* state not clobbered */
            switch (ret) {
                case Z_NEED_DICT:
                    ret = Z_DATA_ERROR;     /* and fall through */
                case Z_DATA_ERROR:
                case Z_MEM_ERROR:
                    (void)inflateEnd(&strm);
                    return ret;
            }
            have = CHUNK - strm.avail_out;
            if (fwrite(out, 1, have, dest) != have || ferror(dest)) {
                (void)inflateEnd(&strm);
                return Z_ERRNO;
            }
        } while (strm.avail_out == 0);
        
        /* done when inflate() says it's done */
    } while (ret != Z_STREAM_END);
    
    /* clean up and return */
    (void)inflateEnd(&strm);
    return ret == Z_STREAM_END ? Z_OK : Z_DATA_ERROR;
}

/* report a zlib or i/o error */
void zerr(int ret)
{
    fputs("zpipe: ", stderr);
    switch (ret) {
        case Z_ERRNO:
            if (ferror(stdin))
                fputs("error reading stdin\n", stderr);
            if (ferror(stdout))
                fputs("error writing stdout\n", stderr);
            break;
        case Z_STREAM_ERROR:
            fputs("invalid compression level\n", stderr);
            break;
        case Z_DATA_ERROR:
            fputs("invalid or incomplete deflate data\n", stderr);
            break;
        case Z_MEM_ERROR:
            fputs("out of memory\n", stderr);
            break;
        case Z_VERSION_ERROR:
            fputs("zlib version mismatch!\n", stderr);
    }
}

/* compress or decompress from stdin to stdout */
int main(int argc, char **argv)
{
    int ret;
    
    /* avoid end-of-line conversions */
    SET_BINARY_MODE(stdin);
    SET_BINARY_MODE(stdout);
    
    /* do compression if no arguments */
    if (argc == 1) {
        ret = def(stdin, stdout, Z_DEFAULT_COMPRESSION);
        if (ret != Z_OK)
            zerr(ret);
        return ret;
    }
    
    /* do decompression if -d specified */
    else if (argc == 2 && strcmp(argv[1], "-d") == 0) {
        ret = inf(stdin, stdout);
        if (ret != Z_OK)
            zerr(ret);
        return ret;
    }
    
    /* otherwise, report usage */
    else {
        fputs("zpipe usage: zpipe [-d] < source > dest\n", stderr);
        return 1;
    }
}
